//
// Created by francklinson on 2021/7/20 AT 20:17.
//
#include <vector>
#include <iostream>
#include <queue>
#include <tuple>
#include <set>
#include <unordered_set>

using namespace std;

class Solution {
private:
    enum direction {
        horizontal, vertical
    };


    // hash函数
    int getHash(int x, int y, direction dir) {
        return 1000 * x + 10 * y + dir;
    }

    void tryAdd(int r, int c, direction s, queue<tuple<int, int, direction>> &q, unordered_set<int> &us) {
        if (!us.count(getHash(r, c, s))) {
            q.emplace(r, c, s);
            us.insert(getHash(r, c, s));
        }
    }

public:
    int minimumMoves(vector<vector<int>> &grid) {
        unsigned int n = grid.size();
        queue<tuple<int, int, direction>> q; /// 队列 状态由 一对坐标 + 姿态（水平或者垂直） 表征
        // 放入初始值
        q.emplace(0, 1, horizontal);
        // 记忆化
        unordered_set<int> memory;
        memory.insert(getHash(0, 1, horizontal));
        int steps = -1;
        while (!q.empty()) {
            auto levelSize = q.size();
            ++steps;
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                int r = get<0>(p), c = get<1>(p);
                direction dir = get<2>(p);
                // 到达终点
                if (r == n - 1 and c == n - 1 and dir == horizontal) return steps;
                /**
                 * 根据姿态，判断四种动作能不能做
                 */
                if (dir == horizontal) {
                    // 横向 右移
                    if (c + 1 < n and grid[r][c + 1] == 0) {
                        tryAdd(r, c + 1, horizontal, q, memory);
                    }
                    if (r + 1 < n and grid[r + 1][c] == 0 and grid[r + 1][c - 1] == 0) {
                        // 横向 下移
                        tryAdd(r + 1, c, horizontal, q, memory);
                        // 顺时针旋转
                        tryAdd(r + 1, c - 1, vertical, q, memory);
                    }
                } else if (dir == vertical) {
                    if (c + 1 < n and grid[r][c + 1] == 0 and grid[r - 1][c + 1] == 0) {
                        // 垂向 右移
                        tryAdd(r, c + 1, vertical, q, memory);
                        // 逆时针旋转
                        tryAdd(r - 1, c + 1, horizontal, q, memory);
                    }
                    // 垂向 下移
                    if (r + 1 < n and grid[r + 1][c] == 0) {
                        tryAdd(r + 1, c, vertical, q, memory);
                    }
                }
            }
        }
        return -1; // 正常应该到不了这一步  会在循环中返回值
    }
};

class Solution2 {
public:

    int hs;

    inline int getHash(int x, int y, int s) { //x y坐标 0 1状态
        return x * 1000 + y * 10 + s;
    }

    inline void getState(int hash, int &x, int &y, int &s) {
        s = hash % 10;
        hash /= 10;
        y = hash % 100;
        hash /= 100;
        x = hash;
    }

    inline void trypush(int x, int y, int s, queue<int> &qe, unordered_set<int> &st) {
        hs = getHash(x, y, s);
        if (!st.count(hs)) {
            st.insert(hs);
            qe.push(hs);
        }
    }


    int minimumMoves(vector<vector<int>> &grid) {
        int n = grid.size();//n*n 正方形网格

        queue<int> qe;
        int step = -1;//步数
        int sq;

        hs = getHash(0, 1, 0);

        qe.push(hs);//初始状态
        unordered_set<int> st{hs};//走过的状态

        int x;
        int y;
        int s;

        while (!qe.empty()) {
            ++step;
            sq = qe.size();

            while (sq--) {
                hs = qe.front();
                qe.pop();

                getState(hs, x, y, s);

                if (x == n - 1 && y == n - 1 && s == 0) return step;

                if (s) {//纵向
                    if (x + 1 < n && !grid[x + 1][y]) trypush(x + 1, y, 1, qe, st); //可以向下爬

                    if (y + 1 < n && x - 1 >= 0 && !grid[x][y + 1] && !grid[x - 1][y + 1]) { //可以转向 平移
                        trypush(x, y + 1, 1, qe, st); //平移
                        trypush(x - 1, y + 1, 0, qe, st);//翻转
                    }

                } else {//横向
                    if (y + 1 < n && !grid[x][y + 1]) trypush(x, y + 1, 0, qe, st); //可以向右爬

                    if (x + 1 < n && y - 1 >= 0 && !grid[x + 1][y] && !grid[x + 1][y - 1]) { //可以转向 平移
                        trypush(x + 1, y, 0, qe, st); //平移
                        trypush(x + 1, y - 1, 1, qe, st);//翻转
                    }
                }
            }
        }

        return -1;

    }
};


int main() {
    vector<vector<int>>
            grid = {{0, 0, 0, 0, 0, 1},
                    {1, 1, 0, 0, 1, 0},
                    {0, 0, 0, 0, 1, 1},
                    {0, 0, 1, 0, 1, 0},
                    {0, 1, 1, 0, 0, 0},
                    {0, 1, 1, 0, 0, 0}};
    vector<vector<int>> grid2{{0, 0, 1, 1, 1, 1},
                              {0, 0, 0, 0, 1, 1},
                              {1, 1, 0, 0, 0, 1},
                              {1, 1, 1, 0, 0, 1},
                              {1, 1, 1, 0, 0, 1},
                              {1, 1, 1, 0, 0, 0}};
    vector<vector<int>> grid3{{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                              {0, 1, 0, 0, 0, 0, 0, 1, 0, 1},
                              {1, 0, 0, 1, 0, 0, 1, 0, 1, 0},
                              {0, 0, 0, 1, 0, 1, 0, 1, 0, 0},
                              {0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
                              {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
                              {1, 0, 0, 1, 0, 0, 0, 0, 0, 0},
                              {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                              {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                              {1, 1, 0, 0, 0, 0, 0, 0, 0, 0}};
    Solution solution;
    cout << solution.minimumMoves(grid) << endl;
    cout << solution.minimumMoves(grid2) << endl;
    cout << solution.minimumMoves(grid3) << endl;
    return 0;
}

